package pers.sloera.leetcode.editor.cn;//给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 
//输入: a = "11", b = "10"
//输出: "101" 
//
// 示例 2: 
//
// 
//输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
//
// 
//
// 注意：本题与主站 67 题相同：https://leetcode-cn.com/problems/add-binary/ 
// Related Topics 位运算 数学 字符串 模拟 👍 26 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// class Solution {
class SolutionII002 {
    //   public static void main(String[] args) {
    //     final SolutionII002 solutionII002 = new SolutionII002();
    //     // System.out.println(solutionII002.addBinary("1010", "1011"));
    //     System.out.println(solutionII002.addBinary("0", "1"));
    //   }
    public String addBinary(String a, String b) {
        // 可能存在进位
        char[] result = new char[Math.max(a.length(), b.length()) + 1];
        int aIndex = a.length() - 1;
        int bIndex = b.length() - 1;
        int carry = 0;
        for (int i = result.length - 1; i >= 0; i--) {
            int left = aIndex >= 0 ? a.charAt(aIndex) - '0' : 0;
            int right = bIndex >= 0 ? b.charAt(bIndex) - '0' : 0;
            final int temp = left + right + carry;
            if (temp > 1) {
                result[i] = (char) ((temp % 2) + '0');
                carry = 1;
            } else {
                result[i] = (char) (temp + '0');
                carry = 0;
            }
            aIndex--;
            bIndex--;
        }
        final StringBuilder stringBuilder = new StringBuilder();
        int noZeroIndex = 0;
        while (noZeroIndex < result.length && result[noZeroIndex] == '0') {
            noZeroIndex++;
        }
        if (noZeroIndex >= result.length) {
            return "0";
        }
        for (int i = noZeroIndex; i < result.length; i++) {
            stringBuilder.append(result[i]);
        }
        return stringBuilder.toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)
